{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #The K Weakest Rows in a Matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #matrix #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #矩阵 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: kWeakestRows"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #矩阵中战斗力最弱的 K 行"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个大小为 <code>m * n</code> 的矩阵 <code>mat</code>，矩阵由若干军人和平民组成，分别用 1 和 0 表示。</p>\n",
    "\n",
    "<p>请你返回矩阵中战斗力最弱的 <code>k</code> 行的索引，按从最弱到最强排序。</p>\n",
    "\n",
    "<p>如果第 <em><strong>i</strong></em> 行的军人数量少于第 <em><strong>j</strong></em> 行，或者两行军人数量相同但<em><strong> i</strong></em> 小于 <em><strong>j</strong></em>，那么我们认为第<em><strong> i </strong></em>行的战斗力比第<em><strong> j </strong></em>行弱。</p>\n",
    "\n",
    "<p>军人 <strong>总是</strong> 排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>mat = \n",
    "[[1,1,0,0,0],\n",
    " [1,1,1,1,0],\n",
    " [1,0,0,0,0],\n",
    " [1,1,0,0,0],\n",
    " [1,1,1,1,1]], \n",
    "k = 3\n",
    "<strong>输出：</strong>[2,0,3]\n",
    "<strong>解释：</strong>\n",
    "每行中的军人数目：\n",
    "行 0 -> 2 \n",
    "行 1 -> 4 \n",
    "行 2 -> 1 \n",
    "行 3 -> 2 \n",
    "行 4 -> 5 \n",
    "从最弱到最强对这些行排序后得到 [2,0,3,1,4]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>mat = \n",
    "[[1,0,0,0],\n",
    " [1,1,1,1],\n",
    " [1,0,0,0],\n",
    " [1,0,0,0]], \n",
    "k = 2\n",
    "<strong>输出：</strong>[0,2]\n",
    "<strong>解释：</strong> \n",
    "每行中的军人数目：\n",
    "行 0 -> 1 \n",
    "行 1 -> 4 \n",
    "行 2 -> 1 \n",
    "行 3 -> 1 \n",
    "从最弱到最强对这些行排序后得到 [0,2,3,1]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == mat.length</code></li>\n",
    "\t<li><code>n == mat[i].length</code></li>\n",
    "\t<li><code>2 <= n, m <= 100</code></li>\n",
    "\t<li><code>1 <= k <= m</code></li>\n",
    "\t<li><code>matrix[i][j]</code> 不是 0 就是 1</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [the-k-weakest-rows-in-a-matrix](https://leetcode.cn/problems/the-k-weakest-rows-in-a-matrix/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [the-k-weakest-rows-in-a-matrix](https://leetcode.cn/problems/the-k-weakest-rows-in-a-matrix/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1,0,0,0],[1,1,1,1,0],[1,0,0,0,0],[1,1,0,0,0],[1,1,1,1,1]]\\n3', '[[1,0,0,0],[1,1,1,1],[1,0,0,0],[1,0,0,0]]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        n = len(mat)\n",
    "        result = []\n",
    "        for i in range(n):\n",
    "            result.append((sum(mat[i]) , i))\n",
    "        result.sort(key = lambda x : (x[0] , x[1]))\n",
    "        return [x[1] for x in result[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        power = list()\n",
    "        for i in range(m):\n",
    "            l, r, pos = 0, n - 1, -1\n",
    "            while l <= r:\n",
    "                mid = (l + r) // 2\n",
    "                if mat[i][mid] == 0:\n",
    "                    r = mid - 1\n",
    "                else:\n",
    "                    pos = mid\n",
    "                    l = mid + 1\n",
    "            power.append((pos + 1, i))\n",
    "\n",
    "        heapq.heapify(power)\n",
    "        ans = list()\n",
    "        for i in range(k):\n",
    "            ans.append(heapq.heappop(power)[1])\n",
    "        return ans\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/the-k-weakest-rows-in-a-matrix/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        n = len(mat)\n",
    "        for i in range(0, n):\n",
    "            mat[i] = sum(mat[i])\n",
    "        #print(mat)\n",
    "        a =  [i for i in range(0, n)]\n",
    "        t = list(zip(mat,a))\n",
    "        temp = sorted(t, key = lambda x:(x[0],x[1]))\n",
    "        res = []\n",
    "        for i in range(0, k):\n",
    "            res.append(temp[i][1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        retVal = []\n",
    "\n",
    "        value = []\n",
    "        for i in range(len(mat)):\n",
    "            soldiers = 0\n",
    "            for col in mat[i]:\n",
    "                if col == 0:\n",
    "                    break\n",
    "                soldiers += 1\n",
    "            value.append([soldiers, i])\n",
    "\n",
    "        heapify(value)\n",
    "        for i in range(k):\n",
    "            retVal.append(heappop(value)[1])\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        return [tup[1] for tup in sorted((sum(mat[i]),i) for i in range(len(mat)))[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: list[list[int]], k: int) -> list[int]:\n",
    "        math = []\n",
    "        for i in range(len(mat)):\n",
    "            t = 0\n",
    "            for j in mat[i]:\n",
    "                if j == 1:\n",
    "                    t += 1\n",
    "                else:\n",
    "                    break\n",
    "            math.append([t, i])\n",
    "        math = sorted(math, key=lambda x:x[0])\n",
    "        ls = []\n",
    "        for i in range(k):\n",
    "            ls.append(math[i][1])\n",
    "        return ls"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        # res = []\n",
    "        # p = 0\n",
    "\n",
    "        # for i in range()\n",
    "\n",
    "        count_dict = {}\n",
    "        for i in range(len(mat)):\n",
    "            count_dict[i] = sum(mat[i])\n",
    "\n",
    "        sort_dict = sorted(count_dict.items(), key = lambda x: x[1])\n",
    "        res = [i[0] for i in sort_dict[:k]]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "\n",
    "        power = [ (idx, sum(line)) for idx, line in enumerate(mat) ]\n",
    "        sorted_power = sorted(power, key=lambda x:(x[1], x[0]))\n",
    "\n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            res.append(sorted_power[i][0])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        return [tup[1] for tup in sorted((sum(mat[i]),i) for i in range(len(mat)))[:k]]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        # 太慢了\n",
    "        # import numpy\n",
    "        # mat = numpy.array(mat)\n",
    "        # list1 = []\n",
    "        # for i in range(k):\n",
    "        #     n = numpy.argmin(numpy.sum(mat,axis=1))\n",
    "        #     list1.append(int(n))\n",
    "        #     mat[n] +=2\n",
    "\n",
    "        # return list1 \n",
    "\n",
    "        list2 = []\n",
    "        for i in range(len(mat)):\n",
    "            mat[i] = [sum(mat[i]),i]\n",
    "        for j in range(k):\n",
    "            list2.append(sorted(mat)[j][1])\n",
    "        \n",
    "        return list2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: list[list[int]], k: int) -> list[int]:\n",
    "        mat2 = []\n",
    "        xuhao = 0\n",
    "        mat3 = []\n",
    "        anw = 0\n",
    "        for mat1 in mat:\n",
    "            mat2.append([sum(mat1), xuhao])\n",
    "            xuhao += 1\n",
    "        mat2.sort()\n",
    "        for _ in range(k):\n",
    "            mat3.append(mat2[anw][1])\n",
    "            anw += 1\n",
    "        return mat3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        nums1 = []\n",
    "        nums2 = []\n",
    "        for j in range( len(mat)):\n",
    "            nums = 0\n",
    "            for i in mat[j]:\n",
    "                if i == 1:\n",
    "                    nums+=1\n",
    "            #nums1[nums] = j\n",
    "            nums1.append([nums,j])\n",
    "        nums1.sort()\n",
    "        #sorted(nums1.keys())\n",
    "        for i in range(k):\n",
    "            nums2.append(nums1[i][1])\n",
    "        return nums2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        ans=[]\n",
    "        for index,value in enumerate(mat):\n",
    "            ans.append((sum(value),index))\n",
    "        # 自定义排序，如果第一个相同，比较第二个\n",
    "        ans.sort(key=lambda x: (x[0],x[1]))\n",
    "        return [v[1] for v in ans[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        n = len(mat)\n",
    "        m = len(mat[0])\n",
    "        res = []\n",
    "        ans = []\n",
    "        for i in range(n):\n",
    "            nums = mat[i]\n",
    "            l = 0\n",
    "            r = len(nums) - 1\n",
    "            while l < r:\n",
    "                mid = l + r + 1 >> 1\n",
    "                if nums[mid] == 1:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            if nums[r] != 0:\n",
    "                res.append([i, r + 1])\n",
    "            else:\n",
    "                res.append([i,0])\n",
    "        res.sort(key=lambda x:x[1])\n",
    "        for i in range(k):\n",
    "            ans.append(res[i][0])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        n = len(mat)\n",
    "        for i in range(n):\n",
    "            mat[i] = [sum(mat[i]), i]\n",
    "        return [a[1] for a in sorted(mat)[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        return [l[1] for l in sorted([[sum(line), i] for i, line in enumerate(mat)])[:k]]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        return sorted([i for i in range(len(mat))], key=lambda x:sum(mat[x]))[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        l =  len(mat)\n",
    "        q = []\n",
    "        for i in range(l):\n",
    "            r = mat[i]\n",
    "            t = 0\n",
    "            for c in r:\n",
    "                if 1 == c:\n",
    "                    t += 1\n",
    "                else:\n",
    "                    break\n",
    "            heapq.heappush(q, (t, i))\n",
    "        ret = []\n",
    "        while k > 0:\n",
    "            ret.append(heapq.heappop(q)[1])\n",
    "            k -= 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        force = []\n",
    "        idx = []\n",
    "        for i in range(len(mat)):\n",
    "            idx.append(i)\n",
    "            force.append(sum(mat[i]))\n",
    "        ans = []\n",
    "        for i in range(k):\n",
    "            num = force.index(min(force))\n",
    "            ans.append(idx[num])\n",
    "            force.pop(num)\n",
    "            idx.pop(num)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        ak = []\n",
    "        for i in range(len(mat)):\n",
    "            ck = sum(mat[i])\n",
    "            ak.append([ck,i])\n",
    "        ak.sort(key = lambda x:x[1])\n",
    "        ak.sort(key = lambda x:x[0])\n",
    "        ans = [ak[i][1] for i in range(k)]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        def check(line):\n",
    "            cnt = 0\n",
    "            for i in range(len(line)):\n",
    "                if line[i] == 0:\n",
    "                    break\n",
    "                cnt += 1\n",
    "            return cnt\n",
    "        n = len(mat)\n",
    "        ans = []\n",
    "        for i, line in enumerate(mat):\n",
    "            ans.append([i, check(line)])\n",
    "        ans = sorted(ans, key=lambda x:x[1])\n",
    "        return [tuple[0] for tuple in ans[:k]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        n,l1 = len(mat), []\n",
    "        for i in range(n):\n",
    "            l1.append((sum(mat[i]), i))\n",
    "        \n",
    "        return [i for i in list(zip(*sorted(l1)))[1]][:k]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        r = []\n",
    "        for i in range(m):\n",
    "            left = 0\n",
    "            right = n - 1\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if mat[i][mid] > 0:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid - 1\n",
    "            if mat[i][left] > 0:\n",
    "                r.append((left, i))\n",
    "            else:\n",
    "                r.append((left - 1, i))\n",
    "        heapq.heapify(r)\n",
    "        res = []\n",
    "        for _ in range(k):\n",
    "            res.append(heapq.heappop(r)[1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        return sorted([i for i in range(len(mat))], key=lambda x:sum(mat[x]))[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        m=len(mat)\n",
    "        n=len(mat[0])\n",
    "        dic={}\n",
    "        for i in range(m):\n",
    "            dic[i]=0\n",
    "            for ch in mat[i]:\n",
    "                if ch==1:\n",
    "                    dic[i]+=1\n",
    "        dd=sorted(dic.items(),key=lambda x:x[1])\n",
    "        ls=[x[0] for x in dd[:k]]\n",
    "        return ls\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        dic = {}\n",
    "        for i in range(len(mat)):\n",
    "            num = mat[i].count(1)\n",
    "            if num in dic:\n",
    "                dic[num].append(i)\n",
    "            else:\n",
    "                dic[num] = [i]\n",
    "        res = []\n",
    "        for i in range(len(mat[0])+1):\n",
    "            if i in dic:\n",
    "                res += dic[i]\n",
    "        return res[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        m = [(i.count(1), idx) for idx, i in enumerate(mat)]\n",
    "        m.sort()\n",
    "        return [i[1] for i in m[:k]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        return sorted(range(len(mat)), key = lambda x: sum(mat[x]))[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, a: List[List[int]], k: int) -> List[int]:\n",
    "        t = [[a[i].count(1), i] for i in range(len(a))]\n",
    "        t.sort(key=lambda x:(x[0], x[1]))\n",
    "        return [t[i][1] for i in range(k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        return [x[0] for x in sorted(enumerate(mat),key= lambda x:x[1].count(1))[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        lst = [(mat[i].count(1), i) for i in range(len(mat))]\n",
    "        return [n[1] for n in sorted(lst)][:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        dic={}\n",
    "        for i in range(len(mat)):\n",
    "            dic[i]=mat[i].count(1)\n",
    "        res=sorted(dic.items(),key=lambda x:(x[1],x[0]))\n",
    "        list1=[]\n",
    "        for i in range(len(res)):\n",
    "            list1.append(res[i][0])\n",
    "        return list1[:k]\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        return sorted(list(range(len(mat))),key = lambda x:sum(mat[x]))[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        n = len(mat)\n",
    "        res = []\n",
    "        rank = list(sum(mat[i]) * 100 + i for i in range(n))\n",
    "        rank.sort()\n",
    "        return list(rank[i]%100 for i in range(k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        return sorted(list(range(len(mat))),key = lambda x:sum(mat[x]))[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        cur = []\n",
    "        for i, m in enumerate(mat):\n",
    "            cur.append([i, sum(m)])\n",
    "        cur.sort(key = lambda x : (x[1], x[0]))\n",
    "        res = []\n",
    "        for c in cur:\n",
    "            res.append(c[0])\n",
    "        return res[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        L = nsmallest(k, enumerate(mat), key=lambda x: (bisect.bisect_left(x[1], 0, key=lambda x: -x), x[0]))\n",
    "        return [x[0] for x in L]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        power = []\n",
    "        for i in range(0,len(mat)):\n",
    "            power.append([i,mat[i].count(1)])\n",
    "        power.sort(key = lambda x:x[1])\n",
    "        result = []\n",
    "        for j in range(0, k):\n",
    "            result.append(power[j][0])\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        cnt = [ (sum(mat[i]), i) for i in range (m) ]\n",
    "        heapq.heapify(cnt)\n",
    "        ans = []\n",
    "        for i in range(k):\n",
    "            ans.append(heapq.heappop(cnt)[1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        tmp = []\n",
    "        for m in mat:\n",
    "            tmp.append(sum(m))\n",
    "        value = sorted(tmp)\n",
    "        res = [-1]*k\n",
    "        for i in range(k):\n",
    "            res[i]=tmp.index(value[i])  # 用index查第1个满足条件的序号\n",
    "            tmp[tmp.index(value[i])]=-1 # 由于可能有多个战斗力相同的序号，因此将上一行代码查到的序号的值置为-1，保证下一次用index查到是战斗力相同的第2个序号\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        for i, j in enumerate(mat):\n",
    "            mat[i] = [sum(j), i]\n",
    "        mat.sort(key=lambda x:x[0])\n",
    "        return [j for i, j in mat[:k]]       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        mat = sorted(enumerate(list(map(sum,mat))),key=lambda x:x[1])\n",
    "        return [mat[i][0] for i in range(k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        row_length = [(sum(mat[i]), i) for i in range(len(mat))]\n",
    "        row_length = sorted(row_length)\n",
    "        return [i[1] for i in row_length[:k]]\n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        temp = []\n",
    "        for i in mat:\n",
    "            temp.append(sum(i))\n",
    "        res = []\n",
    "        for i in range(k):\n",
    "            a = temp.index(min(temp))\n",
    "            temp[a]=101\n",
    "            res.append(a)\n",
    "            \n",
    "        return res\n",
    "        #2 4 1 2 5\n",
    "        #0 1 2 3 4\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        res = []\n",
    "        for idx, rows in enumerate(mat):\n",
    "            res.append((idx, sum(rows)))\n",
    "\n",
    "        res = sorted(res, key=lambda x: x[1])\n",
    "\n",
    "        return [i[0] for i in res[:k]]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        arr = []\n",
    "        for i in range(len(mat)) :\n",
    "            arr.append([sum(mat[i]), i])\n",
    "        \n",
    "        arr.sort()\n",
    "\n",
    "        return [ arr[i][1] for i in range(k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        cnt_list = []\n",
    "        for index, line in enumerate(mat):\n",
    "            cnt_list.append([sum(line), index])\n",
    "        \n",
    "        return [x[1] for x in sorted(cnt_list, key=lambda d:(d[0], d[1]))[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        return [sorted(enumerate(list(map(sum,mat))),key=lambda x:x[1])[i][0] for i in range(k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        ans=[]\n",
    "        for j in range(n):\n",
    "            for i in range(m):\n",
    "                if mat[i][j]==0 and i not in ans:\n",
    "                    if len(ans)==k:\n",
    "                        return ans\n",
    "                    ans.append(i)\n",
    "        return (ans+[i for i in range(m) if i not in ans])[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        res=[]\n",
    "        for i in range(len(mat)):\n",
    "            res.append((sum(mat[i]),i))\n",
    "        res.sort()\n",
    "        rest=[]\n",
    "        for i in range(k):\n",
    "            rest.append(res[i][1])\n",
    "        return rest\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        ans = [[idx, sum(row)] for idx, row in enumerate(mat)]\n",
    "        ans.sort(key= lambda x:x[1])\n",
    "        return [a[0] for a in ans][:k]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        heap = []\n",
    "        \n",
    "        m, n = len(mat), len(mat[0])\n",
    "        i = 0\n",
    "        while i < m:\n",
    "            l, r = -1, n\n",
    "            while l + 1 < r:\n",
    "                mid = l + (r - l) // 2\n",
    "                if mat[i][mid] == 1:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid\n",
    "            power = (l + 1) * 100 + i\n",
    "            heappush(heap, (-power, i))\n",
    "            if len(heap) > k:\n",
    "                heappop(heap)\n",
    "            i += 1\n",
    "        \n",
    "        heap.sort(reverse = True)\n",
    "        return [idx for v,idx in heap]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        res = []\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        for i in range(m):\n",
    "            cnt = 0\n",
    "            for j in range(n):\n",
    "                if mat[i][j] == 1:\n",
    "                    cnt += 1\n",
    "            res.append([i, cnt])\n",
    "        res.sort(key=lambda x: x[1])\n",
    "        return [res[i][0] for i in range(k)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "\n",
    "        record = {}\n",
    "        for i in range(len(mat)):\n",
    "            record[i] = sum(mat[i])\n",
    "\n",
    "        record = sorted(record.items(),  key=lambda d: d[1], reverse=False)\n",
    "        \n",
    "        result = []\n",
    "        for i in range(k):\n",
    "            result.append(record[i][0])\n",
    "        \n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        x = []\n",
    "        for i, s in enumerate(mat):\n",
    "            x.append((sum(s), i))\n",
    "        x.sort(key = lambda x: (x[0], x[1]))\n",
    "        ans = []\n",
    "        for i in range(k):\n",
    "            ans.append(x[i][1])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        s = map(sum, mat)\n",
    "        vi = [(v, i) for i, v in enumerate(s)]\n",
    "        vi.sort()\n",
    "        r = []\n",
    "        for i in range(k):\n",
    "            r.append(vi[i][1])\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        cnt = [ (sum(mat[i]), i) for i in range (m) ]\n",
    "        cnt.sort()\n",
    "        ans = []\n",
    "        order = list(zip(*cnt))\n",
    "        return order[1][:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        nums = []\n",
    "        for i in range(len(mat)):\n",
    "            count = 0\n",
    "            for j in mat[i]:\n",
    "                if j == 1:\n",
    "                    count += 1\n",
    "                else:\n",
    "                    break\n",
    "            nums.append(count)\n",
    "        ans = []\n",
    "        for i in range(k):\n",
    "            ans.append(nums.index(min(nums)))\n",
    "            nums[nums.index(min(nums))] = 199\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        n = len(mat)\n",
    "        res = []\n",
    "        rank = list(sum(mat[i]) * 100 + i for i in range(n))\n",
    "        rank.sort()\n",
    "        return list(rank[i]%100 for i in range(k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        ans = []\n",
    "        for i in enumerate(mat):\n",
    "            i = list(i)\n",
    "            i[1] = i[1].count(1)\n",
    "            ans.append(i)\n",
    "        ans.sort(key=lambda x:x[1])\n",
    "        tmp = []\n",
    "        for i in range(k):\n",
    "            tmp.append(ans[i][0])\n",
    "        return tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        return sorted(list(range(len(mat))),key = lambda x:sum(mat[x]))[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        ans = []\n",
    "        for i,row in enumerate(mat):\n",
    "            ans.append((sum(row), i))\n",
    "            #[2,4,1,2,5]\n",
    "        res = []\n",
    "        #ans.sort(key=lambda x: x[1])\n",
    "        ans.sort()\n",
    "        for i in range(k):\n",
    "            res.append(ans[i][1])\n",
    "            \n",
    "            \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        m=len(mat)    #m行\n",
    "        n=len(mat[0]) #n列\n",
    "        #遍历列，哪一列最先出现0，就表示这一行的1是最少的，这样找全前k个序列就结束\n",
    "        res=[]\n",
    "        for j in range(n):\n",
    "            for i in range(m):\n",
    "                if mat[i][j] == 0 and i not in res:\n",
    "                    if len(res)==k:\n",
    "                        return res\n",
    "                    res.append(i)  #如果还没找到前k个，就一直找\n",
    "        # if res==[]:\n",
    "        #     return [0] #防止出现全是1，没有0 的时候结果为空，但实际上应该是第一列\n",
    "        # else :\n",
    "        #     return res  #不能直接返回res的值，原因是可能满足res的值只有3个，但答案需要前4个最小的索引，会引起报错\n",
    "        return (res + [i for i in range(m) if i not in res])[:k]\n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        def transpose(matrix: list) -> list:\n",
    "            res = [[0]*len(matrix) for i in range(len(matrix[0]))]\n",
    "            for i in range(len(matrix)):\n",
    "                for j in range(len(matrix[0])):\n",
    "                    res[j][i] = matrix[i][j]\n",
    "            return res\n",
    "\n",
    "        mat1 = transpose(mat)\n",
    "        res = []\n",
    "        i = 0\n",
    "        while i<len(mat1):\n",
    "            if sum(mat1[i]) == len(mat): i += 1\n",
    "            else:\n",
    "                index = mat1[i].index(0)\n",
    "                res.append(index)\n",
    "                mat[index][:] = [1]*len(mat1)\n",
    "                mat1 = transpose(mat)\n",
    "        res += list(set([i for i in range(len(mat))])-set(res))\n",
    "        return res[:k] if len(res)>0 else [0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        row=len(mat)\n",
    "        kk=[]\n",
    "        for m in range(row):\n",
    "            kk.append([mat[m].count(1),m])\n",
    "        kk.sort()\n",
    "        s=[]\n",
    "        for i in range(k):\n",
    "            s.append(kk[i][1])\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        ans=[]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if mat[i].count(1)==n:\n",
    "                    ans.append([i,n])\n",
    "                    break\n",
    "                if mat[i][j]==0:\n",
    "                    ans.append([i,j])\n",
    "                    break\n",
    "        ans.sort(reverse=False,key=lambda x:x[1])\n",
    "        return [i[0] for i in ans[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:\n",
    "        res_dicts={}\n",
    "        print(len(mat))\n",
    "        for i in range(len(mat)):\n",
    "            nums=mat[i]\n",
    "            fight=0\n",
    "            for j in range(len(nums)):\n",
    "                if nums[j]==0:\n",
    "                    break\n",
    "                fight+=1\n",
    "            res_dicts[i]=fight\n",
    "        m=dict(sorted(res_dicts.items(),key=lambda x:x[1]))\n",
    "        res=[]\n",
    "        cnt=0\n",
    "        for key in m.keys():\n",
    "            cnt+=1\n",
    "            res.append(key)\n",
    "            if cnt==k:\n",
    "                break\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
